/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

/* 
解法1: 

比较暴力的解法

res1 = parent->val + robHelper(parent->left->left) + robHelper(parent->left->right)
                     robHelper(parent->right->left) + robHelper(parent->right->right)

max(
    res1,
    robHelper(parent->left) + robHelper(parent->right)
);
#############################################################################
解法2: 

执行用时：28 ms, 在所有 C++ 提交中击败了72.54%的用户
内存消耗：24.8 MB, 在所有 C++ 提交中击败了55.92%的用户


记录每一个节点的 robHelper 返回值 信息

res1 = parent->val + robHelper(parent->left->left) + robHelper(parent->left->right)
                     robHelper(parent->right->left) + robHelper(parent->right->right)

max(
    res1,
    robHelper(parent->left) + robHelper(parent->right)
);
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
   
    int robHelper(TreeNode* parent, unordered_map<TreeNode *, int> & TreeNodeMap) {
        /*           parent 
                child    child
                grandchild   grandchild
        */
        if (parent == 0)
            return 0;

        if(TreeNodeMap.find(parent) != TreeNodeMap.end())
        {
            return TreeNodeMap.at(parent);
        }
        
        int res1 = parent->val;
        if(parent->left)
        {
            res1+= robHelper(parent->left->left,TreeNodeMap);
            res1+= robHelper(parent->left->right,TreeNodeMap);
        }
        if(parent->right)
        {
            res1+= robHelper(parent->right->left,TreeNodeMap);
            res1+= robHelper(parent->right->right,TreeNodeMap);
        }
         
        int res =  max(
            res1,
            robHelper(parent->left,TreeNodeMap) + robHelper(parent->right,TreeNodeMap)
            );  
        TreeNodeMap.emplace(parent,res);
        return res;   
    }

    int rob(TreeNode* root) {
        unordered_map<TreeNode *, int> TreeNodeMap;
        return robHelper(root,TreeNodeMap);
    }
    
};
/*
#############################################################################
解法3: 
我们换一种办法来定义此问题

每个节点可选择偷或者不偷两种状态，根据题目意思，相连节点不能一起偷

当前节点选择偷时，那么两个孩子节点就不能选择偷了
当前节点选择不偷时，两个孩子节点只需要拿最多的钱出来就行(两个孩子节点偷不偷没关系)
我们使用一个大小为 2 的数组来表示 int[] res = new int[2] 0 代表不偷，1 代表偷
任何一个节点能偷到的最大钱的状态可以定义为

当前节点选择不偷：当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱
当前节点选择偷：当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数
表示为公式如下


root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) + Math.max(rob(root.right)[0], rob(root.right)[1])
root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;

作者：reals
链接：https://leetcode-cn.com/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

*/

class Solution {
public:
   
    int*  robHelper(TreeNode* parent) {
        /*           parent 
                child    child
                grandchild   grandchild
        */
        int * res = new int[2];
        res[0] = 0;  // 不偷当前节点
        res[1] = 0;  // 偷当前节点
        if (parent == 0)
            return res;
        
        int* left = robHelper(parent->left);
        int* right = robHelper(parent->right);

        res[0] = max(left[0],left[1]) + max(right[0],right[1]);
        res[1] = left[0] + right[0] + parent->val;
        return res;   
    }

    int rob(TreeNode* root) {
         int* res = robHelper(root);
         return max(res[0],res[1]);
    }
    
};